//
// Created by Administrator on 2021/4/9.
//

/*
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
        结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
        例如：
给定 BST [1,null,2,2],

1
\
    2
/
2
返回[2].

提示：如果众数超过1个，不需考虑输出顺序

        进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/


#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
};

class Solution {
    unordered_map<int, int> ans;
public:
    vector<int> findMode(TreeNode *root) {
        dfs(root);
        vector<int> ret;
        int maxVal = 0;
        // 遍历两次hash表，找到众数
        for (auto an : ans) {
            maxVal = max(an.second, maxVal);
        }
        for (auto an:ans) {
            if (an.second == maxVal) {
                ret.push_back(an.first);
            }
        }
        return ret;
    }

    void dfs(TreeNode *root) { // 遍历树，将值和出现次数记录
        if (root == nullptr) return;
        ans[root->val]++;
        dfs(root->left);
        dfs(root->right);
    }

    // AC 没有用到二叉搜索树的性质
};

class Solution2 { // 暴力
private:

    void searchBST(TreeNode *cur, unordered_map<int, int> &map) { // 前序遍历
        if (cur == nullptr) return;
        map[cur->val]++; // 统计元素频率
        searchBST(cur->left, map);
        searchBST(cur->right, map);
    }

    bool static cmp(const pair<int, int> &a, const pair<int, int> &b) {
        return a.second > b.second;
    }

public:
    vector<int> findMode(TreeNode *root) {
        unordered_map<int, int> map;
        vector<int> result;
        if (root == nullptr) return result;
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp); // 给频率排个序
        result.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            if (vec[i].second == vec[0].second)
                result.push_back(vec[i].first);
            else
                break;
        }
        return result;
    }
};

class Solution3 {  // 题解  用上二叉搜索树的性质
public:
    vector<int> answer;
    int base, count, maxCount;

    void update(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.push_back(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer = vector<int>{base};  // 清空并重新赋值结果数组
        }
    }

    void dfs(TreeNode *o) {
        if (!o) {
            return;
        }
        // 中序遍历的结果是一个有序数组
        // 问题就变成找一个有序数组的众数
        // 设置好当前众数 当前众数个数 比较即可
        dfs(o->left);
        update(o->val);
        dfs(o->right);
    }

    vector<int> findMode(TreeNode *root) {
        dfs(root);
        return answer;
    }
};

int main() {
    auto t3 = TreeNode(2);
    auto t2 = TreeNode(2, &t3, nullptr);
    auto t1 = TreeNode(1, nullptr, &t2);
    Solution sol;
    vector<int> v = sol.findMode(&t1);
    for (auto x:v) cout << x << endl;
    return 0;
}